# 循环链表 每个节点指向下一个节点，最后一个节点指向链表的头节点，从而形成一个环
#           循环链表的基本结构由节点（Node）和链表（CircularLinkedList）两部分组成。
# 优点
# 无限循环：可以任意遍历，适用于需要循环处理的场景。
# 简化指针操作：不需要考虑链表的尾部，因为尾节点直接连接到头节点。
# 灵活的空间利用：链表的动态特性使得其在内存利用上相较于数组更加灵活。

# 节点包含数据和下一个节点的指针。
class Node:
    def __init__(self,data):
        self.data = data # 节点的数据
        self.next = Node # 指向下一个节点的指针

# 循环链表的类通常包含一个头指针和一些基本的操作，如插入、删除、遍历等。
class CircularLinkList:
    def __init__(self):
        self.head = None # 链表的头节点

    # 表头插入
    def insert_at_head(self,data):
        new_node = Node(data)

        if not self.head: # 如果表头为空
            self.head = new_node
            new_node.next = self.head
        else:
            cur = self.head
            while cur.next != self.head: # 找到链尾
                cur = cur.next
                cur.next = new_node # 尾节点指向新节点
                new_node.next = self.head # 新节点指向头节点
                self.head = cur.next # 更新头节点